package top.lywivan.complexity;

import java.util.*;
import java.util.stream.Collectors;

public class Solution {

    int[][] direction=new int[][]{
            {0,1},
            {0,-1},
            {-1,0},
            {1,0}
    };

    Set<Character>[] row=new Set[9];
    Set<Character>[] col=new Set[9];
    Set<Character>[] block=new Set[9];

    public void solveSudoku(char[][] board) {
        for(int i=0;i<9;i++){
            row[i]=new HashSet<>();
            col[i]=new HashSet<>();
            block[i]=new HashSet<>();
        }
        List<int[]> emptyIndex=new ArrayList<>();
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(board[i][j]=='.'){
                    emptyIndex.add(new int[]{i,j});
                }else{
                    int currentBlock=(i/3)*3+j/3;
                    row[i].add(board[i][j]);
                    col[j].add(board[i][j]);
                    block[currentBlock].add(board[i][j]);
                }
            }
        }
        backtrack(board,0,emptyIndex.size(),emptyIndex);
    }

    public boolean backtrack(char[][] board,int current,int level,List<int[]> emptyIndex){
        if(current==level){
            return true;
        }
        int[] currentIndex=emptyIndex.get(current);
        int currentRow=currentIndex[0];
        int currentCol=currentIndex[1];
        int currentBlock=currentRow/3*3+currentCol/3;
        for(char c='1';c<'9';c++){
            if(row[currentRow].contains(c)){
                continue;
            }
            if(col[currentCol].contains(c)){
                continue;
            }
            if(block[currentBlock].contains(c)){
                continue;
            }
            board[currentRow][currentCol]=c;
            row[currentRow].add(c);
            col[currentCol].add(c);
            block[currentBlock].add(c);
            boolean res=backtrack(board,current+1,level,emptyIndex);
            if(res){
                return true;
            }
            board[currentRow][currentCol]='.';
            row[currentRow].remove(c);
            col[currentCol].remove(c);
            block[currentBlock].remove(c);
        }
        return false;
    }

    private void dfs(char[][] grid,boolean[][] visited,int x,int y){
        visited[x][y]=true;
        for(int i=0;i<4;i++){
            int[] dir=direction[i];
            x=x+dir[0];
            y=y+dir[1];
            if(x>=0&&x<grid.length&&y>=0&&y<grid[0].length&&!visited[x][y]&&grid[x][y]=='1'){
                dfs(grid,visited,x,y);
            }
        }
    }

    //深度优先搜索，从某一位置开始，获取所有可能的结果
    private void dfs(char[][] board,int row,int col,boolean[][] visited,TrieNode root,List<String> res){
        //如果前缀树中没有当前节点，则返回
        if(!root.containsKey(board[row][col])){
            return;
        }
        //如果当前节点为结束节点，则算一个结果
        if(root.isEnd()){
            res.add(root.word);
        }
        //设置当前节点已被访问
        visited[row][col]=true;
        //drill down
        //上下左右都需要走
        dfs(board,row+1,col,visited,root,res);
        dfs(board,row-1,col,visited,root,res);
        dfs(board,row,col+1,visited,root,res);
        dfs(board,row,col-1,visited,root,res);
        //反悔自己的选择
        visited[row][col]=false;
    }

    //从大到小排序
    private static void sort(int[] coins){
        new PriorityQueue<Integer>((o1,o2)->o1-o2);
        Arrays.sort(coins);
        int n=coins.length-1;
        int temp;
        for(int i=0;i<=n/2;i++){
            temp=coins[i];
            coins[i]=coins[n-i];
            coins[n-i]=temp;
        }
    }

    //记录最少硬币数量
    static int minCount=Integer.MAX_VALUE;

    //dfs回溯
    private static void dfs(int[] coins, int amount, int startIndex,int currentCount){
        //terminal
        if(amount==0){
            minCount=Math.min(minCount,currentCount);
            return;
        }
        if(startIndex>=coins.length){
            return;
        }
        //process current logic
        //获取当前面值最大有多少
        int maxCount=amount/coins[startIndex];
        //贪心算法
        for(int i=maxCount;i>=0&&(currentCount+i)<minCount;i--){
            //获取剩余的金额
            int resAmount=amount-coins[startIndex]*i;
            //drill down
            dfs(coins,resAmount,startIndex+1,currentCount+i);
        }
    }

    private static void reserve(ListNode head){
        ListNode pre=null;
        ListNode next=null;
        ListNode curr=head;
        while(curr!=null){
            next=curr.next;
            curr.next=pre;
            pre=curr;
            curr=next;
        }
    }

    static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public static void main(String[] args) {
        //ListNode l1=new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4,new ListNode(5)))));
        //new Solution().numIslands(new char[][]{new char[]{'1','1','1','1','0'},new char[]{'1','1','0','1','0'}
        //        ,new char[]{'1','1','0','0','0'},new char[]{'0','0','0','0','0'}
        //});
        //new Solution().solveSudoku(new int[]{1,3,2,8,4,9},2);
        //Trie trie = new Trie();
        //trie.insert("apple");
        //trie.search("apple");
        int n=1;
        System.out.println(n-1==0);;
    }
}

class WordTrie {
    public TrieNode root = new TrieNode();
    //根据单词构建字典树
    public void insert(String word) {
        TrieNode node = root;
        for (char c:word.toCharArray()) {
            if (!node.containsKey(c)) {
                node.put(c,new TrieNode());
            }
            node = node.get(c);
        }
        node.setEnd();
        //当前节点如果代表了一个完整单词，则将该单词存储起来
        node.setWord(word);
    }
}
//字典树节点对象
class TrieNode{
    //如果该节点代表了一个单词的结尾,则将该完整单词存储到该节点的word属性中
    public String word;
    public TrieNode[] children;
    public final int R = 26;
    public boolean isEnd;
    public TrieNode(){
        this.children = new TrieNode[R];
    }
    public boolean containsKey (char key) {
        return this.children[key-'a'] !=null;
    }
    public void put (char key,TrieNode node) {
        this.children[key-'a'] = node;
    }
    public TrieNode get (char key) {
        return this.children[key -'a'];
    }
    public void setEnd() {
        this.isEnd = true;
    }
    public boolean isEnd () {
        return this.isEnd;
    }
    public void setWord(String word) {
        this.word = word;
    }
    public String getWord () {
        return this.word;
    }
}


